#include "BinarySearchTree.h"
#include <vector>

 struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

 TreeNode* _build(TreeNode*& _root, int& rooti, int left, int right,
     vector<int>& preorder, vector<int>& inorder)
 {
     if (left > right)
         return nullptr;
     if (left == right)
     {
         return new TreeNode(preorder[rooti++]);
     }

     _root = new TreeNode(preorder[rooti++]);
     int edge = 0;
     while (inorder[edge] != preorder[rooti - 1])
         edge++;
     _root->left = _build(_root->left, rooti, left, edge - 1, preorder, inorder);
     _root->right = _build(_root->right, rooti, edge + 1, right, preorder, inorder);
     return _root;
 }
 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
     int rooti = 0;
     TreeNode* root = nullptr;
     return _build(root, rooti, 0, inorder.size() - 1, preorder, inorder);
 }

int main()
{
    vector<int> pre, in;
    int a1[] = { 1,2 };
    for (auto e : a1)
    {
        pre.push_back(e);
    }
    int a2[] = { 1,2 };
    for (auto e : a2)
    {
        in.push_back(e);
    }
    buildTree(pre, in);
	return 0;
}